package my.algo;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;
import java.nio.file.Paths;
import java.util.*;
import java.util.concurrent.*;

public class LeetCode {
    static class Encrypter {

        int[] keysMap;
        Map<String, List<Integer>> valuesMap;
        char[] keys;
        String[] values;
        String[] dictionary;
        Set<String> dicSet;

        public Encrypter(char[] keys, String[] values, String[] dictionary) {
            this.keys = keys;
            this.values = values;
            this.dictionary = dictionary;
            keysMap = new int[26];
            for (int i = 0; i < keys.length; i++) {
                char c = keys[i];
                keysMap[c - 'a'] = i;
            }
            valuesMap = new HashMap<>();
            for (int i = 0; i < values.length; i++) {
                String value = values[i];
                List<Integer> idxs = valuesMap.get(value);
                if (idxs == null) {
                    idxs = new LinkedList<>();
                    valuesMap.put(value, idxs);
                }
                idxs.add(i);
            }
            dicSet = new HashSet<>();
            for (String str : dictionary) {
                dicSet.add(str);
            }
        }

        public String encrypt(String word1) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < word1.length(); i++) {
                char c = word1.charAt(i);
                sb.append(values[keysMap[c - 'a']]);
            }
            return sb.toString();
        }

        public int decrypt(String word2) {
            int len = word2.length();
            char[] chars = new char[2];
            List<List<Integer>> list = new ArrayList<>(len);
            for (int i = 0; i < len; i += 2) {
                chars[0] = word2.charAt(i);
                chars[1] = word2.charAt(i + 1);
                list.add(valuesMap.get(String.valueOf(chars)));
            }
            chars = new char[len];
            return process(list, 0, chars);
        }

        private int process(List<List<Integer>> list, int idx, char[] chars) {
            if (idx == list.size()) {
                String str = String.valueOf(chars);
                if (dicSet.contains(str)) {
                    return 1;
                }
                return 0;
            }
            List<Integer> temp = list.get(idx);
            int res = 0;
            for (int i : temp) {
                chars[idx] = keys[i];
                res += process(list, idx + 1, chars);
            }
            return res;
        }
    }
/**
 * ["","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"]
 * [[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[30],[],[],[],[],[],[],[],[],[],[]]
 */
    public static void main(String[] args) throws IOException {
        Properties prop = System.getProperties();
        String property = prop.getProperty("base.dir");
        System.out.println(property);
//        var out = new PrintWriter("/data/home/fengbo/Documents/out.txt", StandardCharsets.UTF_8);
//        out.println("aaa");
//        out.flush();
    }


    public String minimizeResult(String expression) {
        String[] arr = expression.split("\\+");
        char[] left = arr[0].toCharArray();
        char[] right = arr[1].toCharArray();

        int min = Integer.MAX_VALUE, minLeft = 0, minRight = right.length;
        int leftMul = 1;
        for (int i = 0; i < left.length; i++) {
            int count1 = Integer.parseInt(String.valueOf(left, i, left.length - i));
            int rightMul = 1;
            for (int j = right.length - 1; j >= 0; j--) {
                int count2 = Integer.parseInt(String.valueOf(right, 0, j + 1));
                int val = leftMul * (count1 + count2) * rightMul;
                if (val < min) {
                    min = val;
                    minLeft = i;
                    minRight = j;
                }
                if (j == right.length - 1) {
                    rightMul =  (right[j] - '0');
                } else {

                    rightMul = rightMul * 10 +  (right[j] - '0');
                }
            }
            if (i == 0) {
                leftMul = (left[i] - '0');
            } else {

                leftMul = leftMul * 10 + (left[i] - '0');
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < left.length; i++) {
            if (minLeft == i) {
                ans.append('(');
            }
            ans.append(left[i]);
        }
        ans.append("+");
        for (int i = 0; i < right.length; i++) {
            ans.append(right[i]);
            if (minRight == i) {
                ans.append(')');
            }
        }
        return ans.toString();
    }

    private int process(int numArrows, int[] aliceArrows, int idx) {
        if (numArrows == 0) {
            return 0;
        }
        if (idx < 0) {
            return 0;
        }
        if (numArrows <= aliceArrows[idx]) {
            return process(numArrows, aliceArrows, idx - 1);
        } else {
            int i = process(numArrows - aliceArrows[idx] - 1, aliceArrows, idx - 1) + idx;
            int j = process(numArrows, aliceArrows, idx - 1);
            return Math.max(i, j);
        }
    }

    public long[] getMin(int n, Map<Integer, List<int[]>> map, int f) {
        long[] b = new long[n];
        Arrays.fill(b, Long.MAX_VALUE);
        b[f] = 0;
        LinkedList<int[]> stack = new LinkedList<>();
        List<int[]> list = map.get(f);
        if (list != null) {
            for (int[] arr : list) {
                stack.push(arr);
            }
        }
        while (!stack.isEmpty()) {
            int[] arr = stack.poll();
            if (arr[2] + b[arr[0]] < b[arr[1]]) {
                b[arr[1]] = arr[2] + b[arr[0]];
                list = map.get(arr[1]);
                if (list != null) {
                    for (int[] cArr : list) {
                        stack.push(cArr);
                    }
                }
            }
        }
        return b;
    }

    static class Info {
        String word;
        int count;

        public Info(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }

    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int ans = 0;
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            int val = 0;
            if (')' == c) {
                val += dp[i - 1];
                int idx = i - val - 1;
                if (idx >= 0 && s.charAt(idx) == '(') {
                    val += 2;
                } else {
                    continue;
                }
                if (idx - 1 >= 0) {
                    val += dp[idx - 1];
                }
                ans = Math.max(ans, val);
            }
            dp[i] = val;
        }
        return ans;
    }

    static class Node {
        int key;
        int val;
        Node next;
        Node prev;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
     static class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
}
